#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
int partSort1(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		while (right > left && a[right] >= a[keyi])
		{
			right--;
		}
		while (right > left && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}
void QuickSort(int* a, int begin, int end)
{
	assert(a);
	if (begin >= end)
	{
		return;
	}
	int keyi = partSort1(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}
void Test()
{
	int a[] = { 9,2,4,8,4,78,543,34,5,5,55,9 };
	QuickSort(a, 0, 11);
	for (int i = 0;i < 12;i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	Test();
	return 0;
}